package com.example.usercenter.utils;

import java.util.List;

public class AlgorithmDistance {
    public static int minEditDistance(List<String> list1, List<String> list2) {
        int m = list1.size(); // 第一个列表的长度
        int n = list2.size(); // 第二个列表的长度

        // 创建一个二维数组 dp，dp[i][j] 表示 list1 的前 i 个元素和 list2 的前 j 个元素之间的最小编辑距离
        int[][] dp = new int[m + 1][n + 1];

        // 初始化第一行和第一列
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i; // 将 list1 的前 i 个元素转换为空列表，需要 i 次删除操作
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j; // 将空列表转换为 list2 的前 j 个元素，需要 j 次插入操作
        }

        // 填充 dp 数组
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 如果当前字符串元素相同，则不需要额外操作
                if (list1.get(i - 1).equals(list2.get(j - 1))) {
                    dp[i][j] = dp[i - 1][j - 1]; // 无操作成本
                } else {
                    // 计算三种操作的代价，并取最小值
                    int insertCost = dp[i][j - 1] + 1; // 插入操作
                    int deleteCost = dp[i - 1][j] + 1; // 删除操作
                    int replaceCost = dp[i - 1][j - 1] + 1; // 替换操作
                    dp[i][j] = Math.min(Math.min(insertCost, deleteCost), replaceCost);
                }
            }
        }

        // 最小编辑距离存储在 dp[m][n] 中
        return dp[m][n];
    }
}
